#include <stdio.h>
#include <stdlib.h>
void print_array(int arr[], int size) {
	int i;
	for (i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

void insertion_sort(int unsorted_array[], int num_elements){
	for (int j = 1; j < num_elements; j++) {
		int key = unsorted_array[j];
		int i = j - 1;
		while (i >= 0 && key < unsorted_array[i]) {
			unsorted_array[i + 1] = unsorted_array[i];
			i--;
		}
		unsorted_array[i + 1] = key;
		print_array(unsorted_array,num_elements);
	}
}


int partition(int L[], int low,  int  high, int total_num_elements){//分割
	int temp = L[low];
	int pivot = L[low];
	while(low < high){
		while(low < high&&L[high] >= pivot){
			--high;
		}
		L[low] = L[high];
		while(low < high && L[low] <= pivot){
			++low;
		}
		L[high]=L[low];
	}
	L[low] = temp;
	print_array(L,total_num_elements);
	return low;
}
void QSort(int L[], int low,  int  high, int total_num_elements){
	if(low < high){
		int  pivotpos = partition(L,low,high,total_num_elements);
		
		QSort(L,low,pivotpos-1,total_num_elements);
		QSort(L,pivotpos+1,high,total_num_elements);
		
	}
}

void quick_sort(int unsorted_array[],int num_elements ){
	int low = 0,high = num_elements-1;
	QSort(unsorted_array,low,high,num_elements);
}

void max_heap_down(int a[], int start, int end)
{
	int c = start;
	int l = 2 * c + 1;//start的左孩子索引
	int tmp = a[c];
	for (; l <= end; c = l, l = 2 * l + 1)//将c设置为其左孩子，l设置为右孩子
	{
		if (l < end && a[l] < a[l + 1])//如果右孩子小于end，并且,右孩子小于左孩子
			l++;       //将l改为左孩子索引
		if (tmp >= a[l])//如果c的孩子中较大的元素大于父亲节点
			break;   //则跳出循环
		else           //否则
		{
			a[c] = a[l];//将父亲节点和比自己大的孩子结点交换
			a[l] = tmp;
		}
	}
}
void heap_sort(int unsorted_array[], int num_elements){
	int i;
	int swap;
	for (i = num_elements / 2 - 1; i >= 0; i--)
		max_heap_down(unsorted_array, i, num_elements - 1);
	for (i = num_elements - 1; i > 0; i--)//设置n-1次循环，因为当n-1个节点都按顺序排好以后，最后一个一定是最小值
	{   swap=unsorted_array[i];
		unsorted_array[i]=unsorted_array[0];
		unsorted_array[0]=swap;
		print_array(unsorted_array,num_elements);
		max_heap_down(unsorted_array, 0, i - 1);
	}
}
void main(){
	int test[10]={4,3,2,1};
	insertion_sort( test, 4);
	printf("\n");
	int test1[10]={3,1,2,5,4};
	QSort(test1,0,4,5);
	printf("\n");
	int test2[10]={10,60,12,40,30,8,70};
	heap_sort(test2,7);
}
